//给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
//
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
//
// 假设每一种面额的硬币有无限个。
//
// 题目数据保证结果符合 32 位带符号整数。
//
//
//
//
//
//
// 示例 1：
//
//
//输入：amount = 5, coins = [1, 2, 5]
//输出：4
//解释：有四种方式可以凑成总金额：
//5=5
//5=2+2+1
//5=2+1+1+1
//5=1+1+1+1+1
//
//
// 示例 2：
//
//
//输入：amount = 3, coins = [2]
//输出：0
//解释：只用面额 2 的硬币不能凑成总金额 3 。
//
//
// 示例 3：
//
//
//输入：amount = 10, coins = [10]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= coins.length <= 300
// 1 <= coins[i] <= 5000
// coins 中的所有值 互不相同
// 0 <= amount <= 5000
//
//
// Related Topics 数组与矩阵 动态规划 👍 1049 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function change(amount: number, coins: number[]): number {
    /*
    1.确定dp数组以及下标的含义
    dp[j]：凑成总金额j的货币组合数为dp[j]

    2.确定递推公式
    dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
    所以递推公式：dp[j] = dp[j] + dp[j - coins[i]]; 即不放coins[i]时的dp[j]和放coins[i]时的dp[j - coins[i]]

    3.dp数组如何初始化
    首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

    本题只能物品外循环背包内循环而不能颠倒，因为颠倒后是求排列问题了(也就是说每次都从物品0开始遍历，例遍历到1 =>(1,5) 后面遍历到5 =>(5,1))
     */


    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let i = 0, length = coins.length; i < length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] = dp[j - coins[i]] + dp[j];
        }
    }
    return dp[amount];
};
//leetcode submit region end(Prohibit modification and deletion)
